In many applications, it is necessary for one process (computer program, module, or thread) executing on a computer system to communicate with one or more other processes executing on the same or other computer systems. The mechanism used to carry out these communications varies from system to system.
One mechanism that has facilitated process-to-process communication in a variety of systems is a “message queue”. As illustrated in FIG. 1, to use a conventional message queue, processes (“enqueue sessions”) send information to other processes (“dequeue sessions”) by placing messages in a message queue 100. The dequeue sessions obtain the information from the enqueue sessions by reading the messages from the message queue 100. When all dequeue sessions that need to read a given message from the message queue 100 have read the given message, the message is removed from the message queue 100. Implementations of message queues are described in U.S. Pat. No. 7,181,482, U.S. Pat. No. 7,185,033, U.S. Pat. No. 7,185,034, U.S. Pat. No. 7,203,706, U.S. Pat. No. 7,779,418, U.S. Pat. No. 7,818,386, U.S. Pat. No. 7,680,793, U.S. Pat. No. 6,058,389, and U.S. Pat. No. 8,397,244, the contents of all of which are incorporated herein by reference.
Unfortunately, conventional implementations of message queues do not scale well. Specifically, as the number of dequeue sessions increases, the contention for the “hot” messages at the head of the queue increases, thereby degrading performance. In addition, when the enqueue sessions and dequeue sessions are spread across several systems, the amount of communication on the interconnect between the systems can become excessive. Furthermore, queue performance may be adversely affected by low memory situations in both single-instance databases and shared-disk databases. Low memory situations may result, for example, when the rate of enqueuing into a queue is faster than the rate of dequeuing from the queue. In such situations, the ever-increasing number of queued messages consumes increasingly large amounts of memory.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.